⟸ pàgina anterior ⟸
Exercici 13 (Tasca 2).
(regular languages, arithmetic progressions, hard exercise, base-2, unary)

Les progressions aritmètiques són regulars

Sigui \boldsymbol{a}=(a_1,a_2,\dots) una progressió aritmètica, és a dir, una seqüència en la qual la diferència entre dos termes consecutius és constant. L’objectiu d’aquest exercici és (d’una manera una mica informal) mostrar que, independentment de la base triada per representar la progressió aritmètica, això dona lloc a un llenguatge regular.

Més en concret:

  1. Demostreu que el llenguatge \{1^m \mid m\in \boldsymbol{a}\} és regular.

  2. Donat n\in \mathbb N, quants estats té el DFA mínim que reconeix el llenguatge \{1^m \mid m\in n\mathbb N\}?

  3. Demostreu que el llenguatge \{w\in \{0,1\}^* \mid \mathtt{value}_2(w)\in \boldsymbol{a}\} és regular.

  4. Donat n\in \mathbb N, quants estats té el DFA mínim que reconeix \{w\in \{0,1\}^* \mid \mathtt{value}_2(w)\in n\mathbb N\} quan n=2^k per a algun k\in \mathbb N? I quan n és senar? I quan n=m2^k per a algun k\in \mathbb N i m és senar?

  5. Demostreu que el llenguatge \{w\in \{0,1,2\}^* \mid \mathtt{value}_3(w)\in \boldsymbol{a}\} és regular.

  6. Demostreu que el llenguatge \{w\in \Sigma^* \mid \mathtt{value}_b(w)\in \boldsymbol{a}\} és regular, on b \ge 2 and \Sigma=\{0,1,2,\dots,b-1\} és un alfabet de dígits.

Recordeu que, per qualsevol b \ge 2, \mathtt{value}_b(w) representa el nombre obtingut interpretant el mot w com un nombre escrit en base b. Per exemple, \mathtt{value}_2(00101)=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+0\cdot 2^3+0\cdot 2^4=1+4=5, \mathtt{value}_3(0121)=1\cdot 3^0+2\cdot 3^1+1\cdot 3^2+0\cdot 3^3=1+6+9=16.